import javax.sound.midi.Soundbank;
import javax.swing.*;
import java.util.HashMap;
import java.util.Set;

/**
 * @author zx
 * @date date 2019-11-29 16:41:09
 */
public class LRUcache {
    private class Node{
        private int value;
        private int key;
        private Node preNode;
        private Node nextNode;
        public Node(int value, int key) {
            this.value = value;
            this.key = key;
        }
        public Node() {
        }
    }

    private Node dummyHead = new Node();
    private Node dummyTail = new Node();
    private int capacity;
    private int size = 0;
    private HashMap<Integer,Node> hashMap = new HashMap<>();


    private void del(Node node){
        Node preNode = node.preNode;
        Node nextNode = node.nextNode;
        preNode.nextNode = nextNode;
        nextNode.preNode = preNode;
        node.preNode = null;
        node.nextNode = null;
    }

    /**
     * 只从头部增加节点
     * @param node
     */
    private void add(Node node){
        Node temp = dummyHead.nextNode;
        dummyHead.nextNode = node;
        node.preNode = dummyHead;
        node.nextNode = temp;
        temp.preNode = node;
    }

    public LRUcache(int capacity) {
        this.capacity = capacity;
        dummyHead.nextNode = dummyTail;
        dummyTail.preNode = dummyHead;
    }

    public void put(int key, int value){
        Node node = hashMap.get(key);
        if(node != null){
            node.value = value;
            del(node);
            add(node);
        }else{
            if(size < capacity) {
                size++;
            }else{
                //超出容量需要删除尾节点，因为每次更新只在头部增加节点
                Node delNode = dummyTail.preNode;
                hashMap.remove(delNode.key);
                del(delNode);
            }
            Node newNode = new Node(key,value);
            add(newNode);
            hashMap.put(key,newNode);
        }
    }

    public int get(int key){
        Node node = hashMap.get(key);
        if(node == null) {
            return -1;
        }

        //访问一次就删除该节点并拉到头部
        del(node);
        add(node);
        return node.value;
    }

    private void print(){
        Node node = dummyHead.nextNode;
        while(node!= dummyTail){
            System.out.print(node.value);
            node = node.nextNode;
        }
        System.out.println("\n");
    }

    public static void main(String[] args) {
        LRUcache lrUcache = new LRUcache(3);
        lrUcache.put(1,1);
        lrUcache.put(2,2);
        lrUcache.put(3,3);
        lrUcache.put(4,4);
        lrUcache.print();
        lrUcache.get(1);
        lrUcache.print();
        lrUcache.put(5,5);
        lrUcache.print();
        lrUcache.get(2);
        lrUcache.print();
    }


}
